package com.xyj.week03;

import java.util.HashMap;
import java.util.Map;

/**
 * 76. 最小覆盖子串
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 *
 *
 *
 * 注意：
 *
 * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 *
 *
 * 示例 1：
 *
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 * 示例 2：
 *
 * 输入：s = "a", t = "a"
 * 输出："a"
 * 示例 3:
 *
 * 输入: s = "a", t = "aa"
 * 输出: ""
 * 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
 * 因此没有符合条件的子字符串，返回空字符串。
 * @author GuXiaoYao
 * @version 1.0.0
 * @since 2021/9/1
 */
public class T7 {
    class Solution {

        public String minWindow(String s, String t) {
            //字符串长度
            int n=s.length();
            //：先定义两个Map，
            //一个是用来存放窗口内有效字符串的,另一个是用来存放固定有效的字符串的
            Map<Character,Integer> validMap=new HashMap<>();
            Map<Character,Integer> windowMap=new HashMap<>();
            //初始化map
            for(char a:t.toCharArray()){
                validMap.put(a,validMap.getOrDefault(a,0)+1);
            }
            //滑动窗口解法
            // 左右窗口
            int right=0, left=0;
            // 有效长度
            int valid=0;
            int start=0,len=Integer.MAX_VALUE;
            //右窗口一直移动，找到满足条件的，开始移动左窗口，寻找最优解
            while(right<n){
                //字符串
                char cur=s.charAt(right);
                if(validMap.containsKey(cur)){
                    //如果是我们想要的字符串，就放入windowMap中
                    windowMap.put(cur,windowMap.getOrDefault(cur,0)+1);
                    //如果这个值放入窗口Map后，出现的次数和我们想要的次数相同的话,有效完成个数+1
                    if(validMap.get(cur).equals(windowMap.get(cur))){
                        valid++;
                    }
                }
                //当满足有效值了，左窗口开始移动
                while(valid==validMap.size()){
                    //更新最小覆盖子串的有效长度和起始点
                    if(right-left+1<len){
                        start=left;
                        len=right-left+1;
                    }
                    char now=s.charAt(left);
                    left++;
                    if(validMap.containsKey(now)){
                        // 右移动时顺便判断，如果被移除的字符位于有效Map中
                        // 比较这个字符，如果这个字符在窗口map中和有效map中的值相等
                        // 那就说明要跳出循环了，
                        if(windowMap.get(now).equals(validMap.get(now))){
                            valid--;
                        }
                        //如果存在的话，就要将map中的这个字符出现的次数减1
                        windowMap.put(now,windowMap.get(now)-1);
                    }
                }
                right++;
            }
            return len== Integer.MAX_VALUE ?"":s.substring(start,start+len);
        }

    }


}
